#include <iostream>
#include "AvlTree.h"
#include <ctime>
#include <cmath>
using namespace std;

    // Test program
int time( int k1, int k2, AvlTree<int> &t);
int main( )
{
    AvlTree<int> t;
    int NUMS = 0;
      int k = 0;
    int i = 0 ,j = 0;
    int k1 = 0, k2 = 0;
  
    int AverageTime = 0 ;
    //测试运行时间与k的关系
    NUMS = 10000;
    for( i = 1; i<=NUMS; i++)
        t.insert( i*2 );
    for( k = 1000; k < NUMS; k +=1000)
      {
	AverageTime = 0;
	for( j=0 ; j < 20; j++)
	  {
	    k1 = rand() % (NUMS*2-k*2);
	    k2 = k1 + 2*k;
	    AverageTime = AverageTime + time ( k1, k2,t);
	  }
	cout << "\n" << endl;
	AverageTime = AverageTime / 20;
	cout <<"K = "<< k << "  ";
	cout << "Average time = " << AverageTime << endl; 
      }

    
    
    t.makeEmpty();

    //测试时间与N的关系
    int GAP = 20;
    for(int itr = 1 ; itr <7 ; itr++){
      k = 19 * itr;
      NUMS = pow( GAP , itr);
	AverageTime = 0;
	for( i = 1; i<=NUMS; i++)
	  t.insert( i );
	
	for( j=0 ; j < 10; j++)
	  {
	    
	     AverageTime = AverageTime + time ( 1, k , t ) ;
	  }
	cout << "\n" << endl;
	AverageTime = AverageTime / 10;
	cout <<"N = "<< NUMS << "  ";
	cout<< "Average time = " << AverageTime << endl; 
	
	t.makeEmpty();
	
      
    }
    return 0;
}
    
int time(int k1, int k2,AvlTree<int> &t)
{
  clock_t begin = 0, end = 0;
  
  begin = clock();
  t.PrintRange( k1 , k2);
  end = clock();
   
    return  end-begin ;
}
